package com.zhn;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
    回溯： 组合排列的练习
 */
public class TestBackTracking {

    public List<Integer> findAnagrams(String s, String p) {
        return null;
    }

    public static void main(String[] args) {
        String s = "abbc";
        LinkedList<String> path = new LinkedList<>();
        List<List<String>> res = new ArrayList<>();
        boolean[] used = new boolean[s.length()];
//        backTracking1(0,s,path,res);
//        backTracking2(s,path,res);
        backTracking3(s,used,path,res);
        System.out.println(res);
    }
    //组合
    public static void backTracking1(int startIndex,String s,List<String> path,List<List<String>> res){
        if(startIndex == 2)
            res.add(new ArrayList<>(path));
        for(int i = startIndex; i < s.length(); i++){
            path.add(String.valueOf(s.charAt(i)));
            backTracking1(startIndex+1,s,path,res);
            path.remove(path.size() - 1);
        }
    }
    //排列
    public static void backTracking2(String s, LinkedList<String> path, List<List<String>> res){
        if(path.size() == 2){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0; i < s.length(); i++){
            if(path.contains(String.valueOf(s.charAt(i))))
                continue;
            path.add(String.valueOf(s.charAt(i)));
            backTracking2(s,path,res);
            path.remove(path.size() - 1);
        }
    }
    //含重复元素的排列
    public static void backTracking3(String s, boolean[] used,LinkedList<String> path, List<List<String>> res){
        if(path.size() == 3)
            res.add(new ArrayList<>(path));
        for(int i = 0; i < s.length(); i++){
            if(i > 0 && s.charAt(i) == s.charAt(i-1) && used[i-1] == false)
                continue;
            if(used[i] == false){
                used[i] = true;
                path.add(s.substring(i,i+1));
                backTracking3(s,used,path,res);
                path.remove(path.size()-1);
                used[i] = false;
            }
        }
    }

}
